#include "preorder.h"
void preorder(Node* root, vector<int>& cache) {
  if (!root)
    return;
  else {
    cache.push_back(root->val);
    for (auto child : root->children) {
      preorder(child, cache);
    }
  }
}
vector<int> preorder(Node* root) {
  vector<int> cache;
  preorder(root, cache);
  return cache;
}